package com.banmao.CarlCamp.Day06;

import java.util.HashMap;
import java.util.HashSet;

/**
 * https://leetcode.cn/problems/4sum-ii/
 */
public class LC454 {


    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        // 不能只用 Set 记录两个数组的和，而要把该和出现的次数也记录下来
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }

        int count = 0;
        // 遍历另外两个数组，如果 Map 中存在 key 为 (0-i-j) 的，做-- 操作
        for (int i : nums3) {
            for (int j : nums4) {
                int sum = i + j;
                count += map.getOrDefault(-sum, 0);
            }
        }
        return count;
    }

    // 错误的想法
    public int fourSumCount_fault(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        // 没有思路 考虑将两个数组的数两两相加放入 Set ，看互为相反数的有多少个？
        HashSet<Integer> set1 = new HashSet<>();
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                set1.add(sum);
            }
        }

        HashSet<Integer> set2 = new HashSet<>();
        for (int i : nums3) {
            for (int j : nums4) {
                int sum = i + j;
                set2.add(sum);
            }
        }

        int count = 0;
        for (Integer s1 : set1) {
            if (set2.contains((-s1))) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        LC454 lc454 = new LC454();
        int[] i1 = {-1,-1};
        int[] i2 = {-1,1};
        int[] i3 = {-1,1};
        int[] i4 = {1,-1};
        System.out.println(lc454.fourSumCount(i1, i2, i3, i4));
    }

}
